package LinkedList;

import Node.ListNode;

public class IsPalindromeSpatialOptimization {

    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        // 优化：快慢指针寻找中点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode left = head;
        // 优化：迭代反转后半链表
        ListNode right = reverse(slow);
        while (right != null) {
            if (left.val != right.val)
                return false;
            left = left.next;
            right = right.next;
        }

        return true;
    }

    private ListNode reverse(ListNode right) {
        if (right == null)
            return null;
        ListNode pre = null, cur = right;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
